package arithmetic;

import java.lang.*;
import java.util.*;

class sort {
    public void QuickSort1(int[] R, int low, int high) {
        if (low < high) {
            int temp = R[low];
            int i = low, j = high;
            while (i < j) {
                while (j > i && R[j] >= temp)
                    j--;// 从右向左扫描，找到第一个小于temp的关键字
                if (i < j) {
                    R[i] = R[j];// 放到temp左边
                    i++;
                }
                while (i < j && R[i] <= temp)
                    i++;// 从左向右扫描，找到第一个大于temp的关键字
                if (i < j) {
                    R[j] = R[i];// 放到temp右边
                    j--;
                }
            } // 一趟排序后枢轴元素temp到达最终位置，左边元素比temp小，右边元素比temp大
            R[i] = temp;
            // 依次对两个子序列进行递归排序
            QuickSort1(R, low, i - 1);
            QuickSort1(R, i + 1, high);
        }
    }
}

public class QuickSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入要排序的个数:");
        int count;
        count = in.nextInt();
        int[] R = new int[count];
        for (int i = 0; i < count; i++) {
            R[i] = in.nextInt();
        }
        int low = 0;
        int heigh = R.length - 1;
        sort QuickSort2 = new sort();
        QuickSort2.QuickSort1(R, low, heigh);
        for (int element : R) {
            System.out.println(element);
        }
    }
}
